1. Field of the Invention
The present invention relates to data compression and more particularly to a method and means for dynamically selecting among coding models to be used during the compression coding of a stream of data to optimize the compression of various portions of the data stream and thus of the entire stream.
2. Problem Solved
To provide an efficient general technique for selecting between two, or more, models for use in compressing data by compression coding techniques, so as to utilize the optimum model for each section of the data being compressed.
3. Prior Art
Various models are known for the compression coding of sets of data. Each establishes a context for the purpose of estimating the probability distribution of the data items or symbols. Typically, a model describing a given entity, such as binary facsimile images, is optimized to provide good compression for a given set of data representing such an image. An example of this is the well-known Huffman coding. Unfortunately, the image model that optimizes compression for one given set of data will most likely perform poorly when applied to a second data set that has significantly different statistical properties. Conversely, a model which is optimized for best compression of the second data set can be expected to perform poorly on the first data set. Although it would be desirable to devise a single model to operate on the entire range of possible data sets, the varying statistical properties of these data sets suggests that any single model optimized for all data sets will provide performance which is a compromise relative to the best possible performance for any single data set or section of a data set. Clearly, the best performance would be realized if the best model could be selected in a dynamic fashion during coding for each data set or portion thereof when being coded.
Although model selection generally has been used in the prior art, the techniques have either:
1. been deterministic, using measures cleverly derived from the data structure, such as disclosed in U.S. Pat. No. 3,394,352, issued July 23, 1968 to R. Wernikoff et al, entitled "Method of and Apparatus for Code Communication", making it effectively a single, more complex, model; or
2. used one of two alternatives, such as disclosed by K. Toyokawa in U.S. Pat. No. 4,901,363, issued Feb. 13, 1990, entitled "System for Compressing Bi-Level Data", involving an arithmetic coding technique for dither halftone images; or
3. used Huffman coding of the selection decision for each block of data, such as disclosed in U.S. Pat. No. 3,830,964, issued Aug. 20, 1974, to D. R. Spencer, entitled "Apparatus and Method for Transmitting a Bandwidth Compressed Digital Signal Representation of a Visible Image".
In the third case, the basic idea involves measuring the coding rate for two different models used in compressing the same block of input data and selecting the most efficient model for that block. However, in this and related prior art, such as, U.S. Pat. No. 4,730,348, issued Mar. 8, 1988 to J. E. MacCrisken, entitled "Adaptive Data Compression System", which use encoding tables, the test interval has always been a block of input data of a given size, and since fixed code assignments have been used, this approach has generated a substantial additional cost in terms of bits needed to code the model selection.
When arithmetic coding is used to compress data, (see G. G. Langdon, "An Introduction to Arithmetic Coding", IBM Journal of Research and Development, Vol. 28, No. 2, pps. 135-149, Mar. 1984), the compression procedure can be divided into two parts:
1. a model section which generates a series of binary decisions from a stream of input symbols and the contexts for those decisions; and PA1 2. an adapter/coder section which estimates the probability for each decision, in the given context, and codes it.
The adaptive nature of this coding process offers the advantage that when a given decision can be predicted with a high probability of success, the cost in terms of compressed bits for making that decision is very low. If this technique is applied to model selection, then when a given data set is compressed much better by one model as compared to another, coding the decision to use the better model does not add much overhead to the compressed data stream.
In "Adaptive Models for Nonstationary Sources", IBM Internal Report RJ 4673, Apr. 24, 1985, M. Wax, J. Rissanen, and K. Mohiuddin, apply the principle, described by present co-inventor J. J. Rissanen in "A Predictive Minimum Description Length Principle", IBM Internal Research Report RJ 5002, January 1986 (also available as "Stochastic Complexity and Modeling" in Ann. of Statistics, September, 1986), to probability estimation for arithmetic coders. The basic idea set forth therein, simply stated, is to maintain a number of measures of probability, and as each symbol is coded, select the measure which currently provides the shortest code stream. In the preferred embodiment, the present invention involves the application, in modified form, of Rissanen's Predictive Minimum Descriptor Length (PMDL) principle, to the problem of dynamic model selection when the models are being coded by arithmetic coding techniques. In particular, the invention applies an inverse form of the PMDL concept--the maximizing of the amount of a data set sent in a given block of compressed data--to provide a mechanism for selecting between two, or more, models.
It is therefore an object of this invention to provide an efficient general technique for selecting among various models for use in compressing data by various compression coding techniques, so as to utilize the optimum model for each section of the data being compressed.